0% completed
Problem Statement
Given a positive integer n, return any valid n-bit gray code sequence.
An n-bit gray code sequence is a sequence containing integers where:
- Each integer is in the inclusive range [0, 2n - 1].
- Sequence always starts with 0.
- All integers are unique in the sequence.
- The
binary representationofevery pairofadjacent integersdiffersbyexactly one bit. - The
binary representationof thefirstandlastintegersdiffersbyexactly one bit.
Examples
-
Example 1
- Input:
n = 4 - Expected Output:
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8] - Justification: This sequence starts at 0 and each subsequent number differs from the previous one by exactly one bit. The sequence covers all numbers from 0 to 15 (which is 2^4 - 1), adhering to the Gray Code property. It also ensures that the first and last numbers (0 and 8) differ by only one bit.
- Input:
-
Example 2
- Input:
n = 1 - Expected Output:
[0, 1] - Justification: With a single bit, the sequence can only be [0, 1], as both numbers differ by exactly one bit, and the sequence starts with 0.
- Input:
-
Example 3
- Input:
n = 3 - Expected Output:
[0, 1, 3, 2, 6, 7, 5, 4] - Justification: This sequence for 3 bits starts at 0, and each subsequent number differs from the previous by exactly one bit. Additionally, the first and last numbers (0 and 4) differ by only one bit, satisfying all the conditions of Gray Code.
- Input:
Solution
The approach to generating a Gray Code sequence for a given bit size, n, exploits the recursive nature of Gray Codes. By starting with a base case for a 0-bit sequence, which is simply [0], we iteratively construct the Gray Code sequence for the next bit size by mirroring the existing sequence and prefixing mirrored parts with 1s.
This method effectively doubles the sequence size at each step, ensuring each number differs by exactly one bit from its predecessor. It's a clever exploitation of binary properties, ensuring that as we progress through bit levels, the essential characteristic of Gray Codes – that each consecutive number differs from the last by exactly one bit – is maintained. This approach is both elegant and efficient, leveraging the mathematical properties of binary numbers to satisfy the problem's constraints.
Step-by-Step Algorithm
-
Initialize the Sequence:
- Start with a sequence containing a single element,
0. This serves as the base case forn = 0, wherenis the number of bits.
- Start with a sequence containing a single element,
-
Iterate Over Bits:
- For each bit from
1ton(inclusive), perform the following steps to construct the Gray Code sequence for that bit level.
- For each bit from
-
Calculate Prefix Value:
- For the current bit level
i, calculate the prefix valueadditionas2^(i-1). This value will be used to generate the mirrored part of the sequence.
- For the current bit level
-
Mirror and Prefix the Sequence:
- Iterate over the current sequence in reverse order.
- For each element, add the
additionvalue calculated in step 3 and append this new value to the sequence. This process mirrors the sequence and prefixes it with1s in the binary representation, ensuring each consecutive number differs by exactly one bit.
-
Repeat Until
nBits:- Repeat steps 2-4 for each bit level until you reach
nbits. The final sequence after the last iteration is the desired Gray Code sequence fornbits.
- Repeat steps 2-4 for each bit level until you reach
Algorithm Walkthrough
Let's consider the Input: n = 4.
-
Initialize the Sequence:
- Start with the sequence:
[0].
- Start with the sequence:
-
Bit Level 1 (
i = 1):addition = 2^(1-1) = 1.- Mirror and prefix: Original sequence
[0], mirrored and prefixed[1]. - New sequence:
[0, 1].
-
Bit Level 2 (
i = 2):addition = 2^(2-1) = 2.- Original sequence:
[0, 1]. - Mirrored and prefixed (with
2added):[3, 2](since1+2=3and0+2=2). - New sequence:
[0, 1, 3, 2].
-
Bit Level 3 (
i = 3):addition = 2^(3-1) = 4.- Original sequence:
[0, 1, 3, 2]. - Mirrored and prefixed (with
4added):[6, 7, 5, 4](since2+4=6,3+4=7,1+4=5,0+4=4). - New sequence:
[0, 1, 3, 2, 6, 7, 5, 4].
-
Bit Level 4 (
i = 4):addition = 2^(4-1) = 8.- Original sequence:
[0, 1, 3, 2, 6, 7, 5, 4]. - Mirrored and prefixed (with
8added): Reverse iterate through the sequence and add8to each:4+8=12,5+8=13,7+8=15,6+8=14,2+8=10,3+8=11,1+8=9,0+8=8.
- New sequence:
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8].
Code
Complexity Analysis
Time Complexity:
The primary reason behind the time complexity being n.
Space Complexity:
Space complexity is also n. The sequence length equals n bits, thereby necessitating storage proportional to the number of elements in the sequence.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity:
Space Complexity: